package pain;

import java.util.Random;

public class Test_1 {
    public static void main(String[] args) {
        int arr[]=new int[10000];
        Random random = new Random();
        for(int i=0;i<arr.length;i++){
            arr[i]=random.nextInt(1000)+1;
        }
        AAA.quicksort(arr,0,arr.length-1);
        for(int data:arr){
            System.out.println(data+" ");
        }
    }
}

class AAA{
    public static void quicksort(int[]arr,int left,int right){
        if(left>=right)
        {
            return ;
        }
        int par=partition_2(arr,left,right);

      //  int par=partition(arr,left,right);
        quicksort(arr,left,par-1);
        quicksort(arr,par+1,right);
    }
    public static int partition(int arr[],int start,int end){
        int i=start;
        int pivot=arr[start];
        while(start<end){
            while(start<end&&arr[end]>=pivot){//右边的数如果大于pivot则end--，直至找到比pivot小的数为止
                end--;
            }
            while(start<end&&arr[start]<=pivot){//左边的数如果小于pivot则start++，直至找到比pivot大的数为止
                start++;
            }
            //找到数据后进行数据交换
            swap(arr,start,end);
        }
        //此时start=end，需要交换其与pivot，pivot下标为i;
        swap(arr,i,start);
        //返回
        return start;
    }

    public static void swap(int[]arr,int i,int j){
        int tem=arr[i];
        arr[i]=arr[j];
        arr[j]=tem;
    }

    //插空法
    public static int partition_2(int[]arr,int start,int end){
        int i=start;
        int pivot=arr[start];
        while(start<end){
            while(start<end&&arr[end]>=pivot){
                end--;
            }
            arr[start]=arr[end];
            while(start<end&&arr[start]<=pivot){
                start++;
            }
            arr[end]=arr[start];
        }
        arr[start]=pivot;//将抽出的值赋给start
        return start;
    }
}
